package Hot_100;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.stream.Stream;

/*
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
链接：https://leetcode.cn/problems/two-sum

思路:
    1) 最普通的做法就是使用两层for循环来找到两数和(暴力法) 时间复杂度为 O(n^2)

问题:
    处理数组的输入，什么时候停止输入
* */
public class T1_twoSum {

    @Test
    public void test() {
        int[] nums = new int[]{3, 2, 4};
        int[] ans = twoSum(nums, 6);
        for (int i : ans) {
            System.out.print(i+" ");
        }

    }


    // 双指针
    public int[] twoSum(int[] nums, int target) {
        if (nums == null) {
            return null;
        }
        int[] arrays = Arrays.copyOf(nums, nums.length);
        Arrays.sort(arrays);
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int now = arrays[left] + arrays[right];
            if (now < target) {
                left++;
            } else if (now > target) {
                right--;
            } else {
                return new int[]{findFirstIndex(arrays[left], nums), findLastIndex(arrays[right], nums)};
            }
        }
        return null;
    }

    private int findFirstIndex(int num, int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                return i;
            }
        }
        return -1;
    }

    private int findLastIndex(int num, int[] nums) {
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == num) {
                return i;
            }
        }
        return -1;
    }


    //    解法1：暴力求法
    public int[] twoSum_test1(int[] nums, int target) {
        int len=nums.length;    //接收数组的长度
        for (int i = 0; i < len-1; i++) {
            for (int j = i+1; j < len; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        throw new IllegalArgumentException("no two sum solution"); //参数不合法的异常
    }

//    解法2：空间换时间（哈希表法）
    public int[] twoSum_test2(int[] nums, int target) {
        int len=nums.length;
        HashMap<Integer, Integer> map = new HashMap<>(len-1);   //指定HashMap的初始化长度（避免扩容影响效率）

        for (int i = 0; i < len; i++) { // 查找 target-nums[i]的值是否在Hash表中
            if(map.containsKey(target-nums[i])){    //如果在表中，可以通过map.get(target-nums[i])得到另一个数的下标
                return new int[]{i,map.get(target-nums[i])};
            }else { // 如果不存在则将该数及其下标存入Hash表中
                map.put(nums[i],i);
            }
        }
        throw new IllegalArgumentException("no two sum solution");
    }

}
